package algorithms.algorithm.sort;

public class InsertationSort {
	public static void sort(int[] array) {
		for (int j = 1; j < array.length; ++j) {
			int key = array[j];
			int i = j - 1;
			while (i > -1 && array[i] > key) {
				array[i + 1] = array[i];
				i = i - 1;
			}
			array[i + 1] = key;
		}
	}

	public static void main(String[] args) {
		int[] arr = { 5, 2, 4, 6, 1, 3 };
		InsertationSort.sort(arr);
		for (int i : arr) {
			System.out.println(i);
		}
	}
}
